/* Author: DO HOANG HAI
 * Main.java
 *
 * Created on June 2, 2006, 2:08 PM
 *
 * Description: This project demonstrates  how to use heap sort algorithm to sort an one-dimension array
 */

package heap;

/**
 *
 * @author hai
 */
public class Main {
    
    
     private static int[] array={5,4,-2,-6,-98,-7};
     private static Heap heap=new Heap();
     
    /** Creates a new instance of Main */
    public Main() {
    }
    
    /**
     * @param args the command line arguments
     */
    public static void main(String[] args) {
        // TODO code application logic here
        inputData();
       
        sort();
        displayResult();
            
        
    }
    public static void inputData(){
        for (int i=0; i<array.length; i++)
            heap.insert(array[i]);
        
        
    }
    public static void sort(){
        for (int i=0; i<array.length; i++)
            array[i]=heap.deleteLeast();
        
    }
    public static void displayResult(){
         for (int index=0; index<array.length; index++)
            System.out.print("  "+ array[index]);
    }
    
    
    
}
class Heap{
    int hole;
    int[] ar=new int[20];
            
    public Heap(){
        hole=0;       
    }
    public void insert(int i){
        int temp=hole;
        while (hole!=0 && parent(hole)>i){
           
            ar[hole]=parent(hole);
            hole=(hole-1)/2;
            
        }
        if (hole==0) ar[0]=i;
        else ar[hole]=i;
        hole=temp+1;
        
    }
    public int deleteLeast(){
        int i=0;
        int temp=ar[0];
        for(;;){
            if (hasNoChild(i)){
                ar[i]=ar[hole-1];
                hole--;
                break;
            }
            if (hasOneChild(i)){
                ar[i]=ar[hole-1];
                hole--;
                break;
            }
            if (hasTwoChildren(i)){
                int min;
                if (ar[i*2+1]<ar[i*2+2]) min=i*2+1;
                else min=i*2+2;
                if (ar[min]>ar[hole-1]){
                    ar[i]=ar[hole-1];
                    hole--;
                    break;
                }
                else{
                    ar[i]=ar[min];
                    i=min;
                }
                
            }
                
        }
        return temp;
    }
    public boolean hasTwoChildren(int index){
        return (hole>index*2+2);
        
    }
    public boolean hasNoChild(int index){
        return (hole<=index*2+1);
    }
    public boolean hasOneChild(int index){
        return (!hasTwoChildren(index)&&!hasNoChild(index));
    }
    public int parent(int hole){
        return ar[(hole-1)/2];
    }
}

